package leetcode_zh

import (
	"math"
	"sort"
)

/**
 * @Description: 1027. 最长等差数列 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/5/29 13:23
 **/
func longestArithSeqLength(nums []int) int {
	var n = len(nums)
	var dp = make([][1001]int, n)
	var maxLen = 0 //保存结果
	for i := 1; i < n; i++ {
		for j := 0; j < i; j++ {
			var d = nums[i] - nums[j] + 500   //统一加偏移量，使下标非负
			dp[i][d] = dp[j][d] + 1           //根据 d 去填充dp[k][d]
			maxLen = getMax(maxLen, dp[i][d]) //维护最大值
		}
	}
	return maxLen + 1

}

/**
 * @Description: 6. Z 字形变换 中等
 * @Keyword: 模拟索引变换
 * @Author: kami
 * @Date: 2022/5/29 17:47
 **/
func convert(s string, numRows int) string {
	if numRows < 2 {
		return s
	}
	var rows = make([][]byte, numRows)
	var idx = 0
	var flag = -1
	for i := 0; i < len(s); i++ {
		rows[idx] = append(rows[idx], s[i])
		if idx == 0 || idx == numRows-1 {
			flag = -flag
		}
		idx += flag
	}
	var res string
	for i := 0; i < numRows; i++ {
		res += string(rows[i])
	}
	return res
}

/**
 * @Description: 26. 删除有序数组中的重复项 简单
 * @Keyword: 保持相对顺序
 * @Author: kami
 * @Date: 2022/5/25 21:15
 **/
func removeDuplicates(nums []int) int {
	var exist = make(map[int]bool)
	var removeIdx = -1
	for i := 0; i < len(nums); i++ {
		var duplicate = exist[nums[i]]
		if removeIdx == -1 && duplicate {
			removeIdx = i
		}
		if !duplicate && removeIdx > -1 {
			nums[removeIdx] = nums[i]
			removeIdx++
		}
		exist[nums[i]] = true
	}
	if removeIdx == -1 {
		return len(nums)
	}
	return removeIdx

}

/**
 * @Description: 80. 删除有序数组中的重复项 II 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/5/30 20:07
 **/
func removeDuplicatesMiddle(nums []int) int {
	if len(nums) <= 2 {
		return len(nums)
	}

	var i = 0
	for _, n := range nums {
		if i < 2 || n > nums[i-2] {
			nums[i] = n
			i++
		}
	}
	return i
}

/**
 * @Description: 56. 合并区间 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/5/31 12:44
 **/
func merge(intervals [][]int) [][]int {
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	res := [][]int{}
	prev := intervals[0]

	for i := 1; i < len(intervals); i++ {
		cur := intervals[i]
		// 前尾小于现首部，不重合
		if prev[1] < cur[0] {
			res = append(res, prev)
			prev = cur
		} else { // 有重合，更新前尾为大者
			prev[1] = getMax(prev[1], cur[1])
		}
	}
	res = append(res, prev)
	return res
}

/**
 * @Description: 1438. 绝对差不超过限制的最长连续子数组 中等
 * @Keyword: 滑动窗口
 * @Author: kami
 * @Date: 2022/6/4 16:52
 **/
func longestSubarray(nums []int, limit int) int {
	left, right := 0, 0
	n := len(nums)
	ans := 0
	maxQueue, minQueue := []int{}, []int{} //存储窗口内，最大值，和最小值
	for right < n {
		//窗口右边界右移，更新窗口内部最大值和最小值
		for len(maxQueue) > 0 && maxQueue[len(maxQueue)-1] < nums[right] {
			maxQueue = maxQueue[:len(maxQueue)-1]
		}
		maxQueue = append(maxQueue, nums[right])
		for len(minQueue) > 0 && minQueue[len(minQueue)-1] > nums[right] {
			minQueue = minQueue[:len(minQueue)-1]
		}
		minQueue = append(minQueue, nums[right])
		right++

		//窗口左边界左移
		for maxQueue[0]-minQueue[0] > limit {
			if nums[left] == maxQueue[0] { //左边界为最大值
				maxQueue = maxQueue[1:]
			}
			if nums[left] == minQueue[0] { //左边界为最小值
				minQueue = minQueue[1:]
			}
			left++
		}

		ans = getMax(ans, right-left)
	}
	return ans
}

/**
 * @Description: 136. 只出现一次的数字 简单
 * @Keyword: 异或运算
 * @Author: kami
 * @Date: 2022/6/7 17:46
 **/
func singleNumber(nums []int) int {
	var res = nums[0]
	for i := 1; i < len(nums); i++ {
		res ^= nums[i]
	}
	return res
}

/**
 * @Description: 55. 跳跃游戏 中等
 * @Keyword: 窗口
 * @Author: kami
 * @Date: 2022/6/8 9:33
 **/
func canJump(nums []int) bool {
	var maxIdx = nums[0]
	var n = len(nums) - 1
	for i := 0; i <= maxIdx; i++ {
		if i+nums[i] > maxIdx {
			maxIdx = i + nums[i]
		}
		if maxIdx >= n {
			return true
		}

	}
	return false
}

/**
* @Description: 287. 寻找重复数 中等
* @Keyword:
      快慢指针思想, fast 和 slow 是指针, nums[slow] 表示取指针对应的元素
      注意 nums 数组中的数字都是在 1 到 n 之间的(在数组中进行游走不会越界),
      因为有重复数字的出现, 所以这个游走必然是成环的, 环的入口就是重复的元素,
      即按照寻找链表环入口的思路来做
* @Author: kami
* @Date: 2022/6/11 15:50
**/
func findDuplicate(nums []int) int {
	var fast = nums[nums[0]]
	var slow = nums[0]
	for {
		fast = nums[nums[fast]]
		slow = nums[slow]
		if fast == slow {
			fast = 0
			for nums[slow] != nums[fast] {
				fast = nums[fast]
				slow = nums[slow]
			}
			return nums[slow]
		}
	}
}

/**
 * @Description: 283. 移动零 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/12 12:24
 **/
func moveZeroes(nums []int) {
	var zeroIdx = -1
	for i := 0; i < len(nums); i++ {
		if nums[i] == 0 && zeroIdx == -1 {
			zeroIdx = i
		}
		if nums[i] != 0 && zeroIdx != -1 {
			nums[zeroIdx], nums[i] = nums[i], nums[zeroIdx]
			zeroIdx++
		}
	}
}

/**
 * @Description: 560. 和为 K 的子数组 中等
 * @Keyword: 前缀和map
 * @Author: kami
 * @Date: 2022/6/13 12:21
 **/
func subarraySum(nums []int, k int) int {
	count, pre := 0, 0
	m := map[int]int{}
	m[0] = 1
	for i := 0; i < len(nums); i++ {
		pre += nums[i]
		if v, ok := m[pre-k]; ok {
			count += v
		}
		m[pre] += 1
	}
	return count
}

func subarraySum560(nums []int, k int) int {
	count := 0
	for start := 0; start < len(nums); start++ {
		sum := 0
		for end := start; end >= 0; end-- {
			sum += nums[end]
			if sum == k {
				count++
			}
		}
	}
	return count
}

/**
 * @Description: 581. 最短无序连续子数组 中等
 * @Keyword: 寻找左右标志位, 1.无序区间比左区间最大值大 2.无序区间比右区间最小值小
很简单，如果最右端的一部分已经排好序，这部分的每个数都比它左边的最大值要大，同理，如果最左端的一部分排好序，这每个数都比它右边的最小值小。
所以我们从左往右遍历，如果i位置上的数比它左边部分最大值小，则这个数肯定要排序，
就这样找到右端不用排序的部分，同理找到左端不用排序的部分，它们之间就是需要排序的部分
 * @Author: kami
 * @Date: 2022/6/18 9:21
 **/
func findUnsortedSubarray(nums []int) int {
	n := len(nums)
	minn, maxn := math.MaxInt64, math.MinInt64
	left, right := -1, -1
	for i, num := range nums {
		// 寻找最大值
		if maxn > num {
			right = i
		} else {
			maxn = num
		}
		// 寻找最小值
		if minn < nums[n-i-1] {
			left = n - i - 1
		} else {
			minn = nums[n-i-1]
		}
	}
	if right == -1 {
		return 0
	}
	return right - left + 1
}
